package _16_combination_sum_iii

//func combinationSum3(k int, n int) [][]int {
//	var res [][]int
//	var list []int
//	var helper func(k int, n int, list []int, startIndex int)
//	helper = func(k int, n int, list []int, startIndex int) {
//		if sum(list) == n && len(list) == k {
//			tmp := make([]int, len(list))
//			copy(tmp, list)
//			res = append(res, tmp)
//			return
//		}
//
//		for i := startIndex; i < n; i++ {
//			list = append(list, i)
//			helper(k, n, list, i+1)
//			list = list[:len(list)-1]
//		}
//	}
//	helper(k, n, list, 1)
//	return res
//}
//
//func sum(list []int) int {
//	var o int
//	for _, v := range list {
//		o += v
//	}
//	return o
//}
//

func combinationSum3(k, n int) [][]int {
	res := [][]int{}
	list := []int{}

	var helper func(startIndex int, sum int)
	helper = func(startIndex int, sum int) {
		if sum == 0 && len(list) == k {
			res = append(res, append([]int{}, list...))
			return
		}

		if sum < 0 || len(list) > k {
			return
		}

		for i := startIndex; i <= 9; i++ {
			list = append(list, i)
			helper(i, sum-i)
			list = list[:len(list)-1]
		}
	}
	helper(1, n)
	return res
}
